package com.gitee.jsbd.algorithm.sort;

import java.util.Arrays;

/**
 * 希尔排序 原地排序 不稳定 （最好：O(n)   最坏：O(n^2) 平均：O(n*log2n)）
 * <p>
 * 将无序数组分割为若干个子序列，子序列不是逐段分割的，
 * 而是相隔特定的增量的子序列，对各个子序列进行插入排序；
 * 然后再选择一个更小的增量，再将数组分割为多个子序列进行排序......最后选择增量为1，
 * 即使用直接插入排序，使最终数组成为有序。
 * </p>
 */
public class ShellSort {

    public static void shellSort(int[] data) {

        int d = data.length / 2;
        int count = 1;
        while (d >= 1) {

            for (int i = d; i < data.length; i++) {
                int value = data[i];
                int j = i - d;
                for (; j >= 0; j -= d) {
                    if (data[j] > value) {
                        data[j + d] = data[j];
                    } else {
                        break;
                    }
                }
                data[j + d] = value;

                System.out.print("d = " + d + "时，第" + count + "次遍历后：");
                System.out.println(Arrays.toString(data));
                count++;
            }
            d = d / 2;

        }

    }


    public static void main(String[] args) {
        int[] data = new int[]{5, 8, 7, 9, 1, 2};
        System.out.print("==初始化==：");
        System.out.println(Arrays.toString(data));

        shellSort(data);

        System.out.println(Arrays.toString(data));
    }

}
